#include <stdio.h>
#include <malloc.h>
//#include "stdlib.h"
//1.实现二叉树，要实现二叉链表的节点
//二叉树  binary tree  BT
//二叉搜索树 binary search tree BST
#define MAXSIZE 10

typedef char ElementType;
typedef  struct node{
    //1.数据项
    ElementType data;
    //2.地址项
    struct node *left;
    struct node *right;
} BTNode;
//1.创建一个结点并存储传递过来的数据
/*
 * 函数名：creatNode()
 * 输入：要存储的元素 data
 * 输出：返回创建好的结点
 * */
BTNode *createNode(ElementType data){
    //1.创建结点
    BTNode *node=malloc(sizeof(BTNode));
    //2.存放数据
    node->data=data;
    node->left=NULL;
    node->right=NULL;

    return node;
}

/*
 * 中序遍历
 * 函数名：inOrder()
 * 输入：树（根结点）
 * 输出：无
 * */
void inOrder(BTNode *root){
    //如果树不为空，进行遍历
    if(root){
        //遍历过程：
       // （1）中序遍历左子树
        inOrder(root->left);
       // （2）访问根节点
        printf("%c ",root->data);
       // （3）中序遍历右子树
        inOrder(root->right);
    }
}
// 返回值类型 函数名（参数1，参数2，....）{
     //函数体
// }
// 返回值类型 函数体有return  void
//动态创建二叉树   从控制台输入一串字符，根据字符创建二叉树
/*
 * 函数名：createBinTree()
 * 输入：根
 * 输出：返回二叉树（二叉树的根结点）
 * */
BTNode *createBinTree(BTNode *root){
    //从控制台获取输入字符
    char str;
    scanf("%c",&str);
  //  若输入的是一个“#”字符，则表明该二叉树为空树，即root=NULL;
  if(str=='#'){
      root=NULL;
  }
  else{//  否则输入的字符应该付给root->data，之后依次递归即那里它的左子树和右子树。
      root= malloc(sizeof(BTNode));
      root->data=str;
      root->left= createBinTree(root->left);
      //root->right= createNode(root->right);
      root->right= createBinTree(root->right);
  }
    return root;
}
//队列实现
//1.定义一个结构体
/*typedef BTNode * ElementType2;
typedef struct queue Queue;
struct queue{
    //1.数据项：用数组来实现
    ElementType2 data[MAXSIZE];
    //2.地址项：两个变量，存储首尾的下标值
};
//2.操作
//2.1 创建队列 createQueue() 返回值：队列 输入：无
Queue *createQueue();
//2.2 进队 EnQueue() 输入值：插入的数值 输出:无
void Enqueue(Queue queue,ElementType2 data);
//2.3 出队 DelQueue()
ElementType2 DelQueue(Queue queue);
//2.4 判断是否为空 IsEmpty()
int IsEmpty(Queue queue);*/
//2.5 判断是否队满 IsFull()
//层序遍历
/*
 * 思路：借助队列
 * 函数名：levelOrder()
 * 输入：树（树的根结点）
 * 输出：在函数里将结点打印出来，无外部输出 void
 * */
void *levelOrder(BTNode *root){
    //1.创建队列
    //Queue *queue =createQueue();
    BTNode *data[100];//数据项
    int front=0;
    int rear=0;
    //2.根结点进队
    BTNode *tmp;
    if(root){
       // Enqueue(queue,root);
       data[rear]=root;
       rear++;
        while(front!=rear)//直到队列为空
        {
            //3.1 队首结点出队
            //tmp = DelQueue(queue);
            tmp = data[front];
            front++;
            //3.2 打印该结点的值（相当于访问）
            printf("%c ",tmp->data);
            //3.3 若子结点存在，则该结点的子结点进队
            if(tmp->left){
               // Enqueue(queue,tmp->left);
                data[rear]=tmp->left;
                rear++;
            }
            if(tmp->right){
                //Enqueue(queue,tmp->right);
                data[rear]=tmp->right;
                rear++;
            }
        }
    }
}
//AB#FL###DI###

//求叶子结点的数量
/*
 * 1.判断是否为叶子结点
 *  node.left==NUll&&node.right==NULL 可以判定Node是叶子结点
 * 2.整棵树的叶子结点数量 =左子树的叶子结点数量+右子树的叶子结点数量
 * f(root)=f(f.left)+f(f.right)
 *
 * 函数名：left_count()
 * 输入：树（树的根结点）
 * 输出：叶子结点的数量 数据类型 int
 * */
int left_count(BTNode *root){
    //1.树为空
    if(root==NULL)
        return 0;
    //2 树不为空
    //2.1 如果结点为叶子结点
    if(root->left==NULL&&root->right==NULL)
        return 1;
    //2.2 整棵树的叶子数量=左子树+右子树
   return left_count(root->left)+ left_count(root->right);
}
int main() {


  //  printf("Hello, World!\n");
  //传入的是A,B,C,D这些字符，字符被放到结点里，结点按照树的关系连接起来
  //1.创建6个结点出来
    BTNode *nodeA= createNode('A');
    BTNode *nodeB= createNode('B');
    BTNode *nodeD= createNode('D');
    BTNode *nodeF= createNode('F');
    BTNode *nodeI= createNode('I');
    BTNode *nodeL= createNode('L');
    //2.按照逻辑关系进行连接
    nodeA->left=nodeB;
    nodeA->right=nodeD;
    nodeB->right=nodeF;
    nodeF->left=nodeL;
    nodeD->left=nodeI;

    inOrder(nodeA);


    printf("测试创建二叉树\n");
    //BTNode *BT;
    printf("层序遍历\n");
    levelOrder(nodeA);
    /*
     *       A
     *     /   \
     *    B     D
     *      \   /
     *      F   I
     *     /
     *    L
     * */
/*    BT = createBinTree(BT);
    printf("新创建的二叉树的中序遍历：\n");
    inOrder(BT);*/
    int n = left_count(nodeA);
    printf("叶子结点的数量：%d",n);


  return 0;
}
